
#include "VEBTree.h"
#include "BinaryHeap.h"
#include "FibonacciHeap.h"
#include "RBTree.h"
#include "Tester.h"
#include "assert.h"

#ifdef linux

#else
  #include <conio.h>
#endif
using namespace algo;
using namespace std;

struct Node {
  Node(int x) : x(x) {}
  int x;
};

class QueueTester : public Tester {
public:
  void runInsert(PriorityQueue<int> &Q) {
    int len = 100000;

    std::vector<int> items;
    for (size_t i = 0; i < len; i++) {
      items.push_back(i);
    }

	cout << "Insertions/time:" << endl;
	unsigned long long start = getTime();
	unsigned long long end = 0;
	for (size_t j = 0; len + j <= 8000000; j += 100000) {
	   start = getTime();
       for (size_t i = 0; i < len + j; i++) {
         PriorityQueueNode<int> *n = Q.insert(items[i]);
       }
	   end = getTime() - start;
	   cout << len + j << " " << end << endl;
	   for (size_t k = 0; k < len + j; k++) {
		   Q.deleteMin();
	   }
	}
  }

  void runDelete(PriorityQueue<int> &Q) {
    int len = 100000;

    std::vector<int> items;
    for (size_t i = 0; i < len; i++) {
      items.push_back(i);
    }

//    random_shuffle(items.begin(), items.end());

	std::vector<PriorityQueueNode<int>*> list;
	cout << "Deletions/time:" << endl;
	unsigned long long start = getTime();
	unsigned long long end = 0;
	for (int j = 0; len + j <= 8000000; j += 100000) {
       for (size_t i = 0; i < len; i++) {
         PriorityQueueNode<int> *n = Q.insert(items[i]);
         list.push_back(n);
       }
	   start = getTime();
	   for (size_t i = 0; i < len; i++) {
         Q.deleteNode(list[i]);
       }
	   end = getTime() - start;
	   cout << len + j << " " << end << endl; 
	   list.clear();
	}
  }

};


int main() {
  VEBTree<int, int> *tree = new VEBTree<int, int>();
  BinaryHeap<int> heap;
  FibonacciHeap<int> fheap;

  //QueueTester QT;
  //QT.runInsert(*tree);
  //delete tree;
  //QT.runInsert(heap);
  //QT.runInsert(fheap);


  std::cout << "Hello" << std::endl;

  //std::cout << tree.lookup(23)->x << std::endl;
  //std::cout << tree.lookup((3<<16)+1)->x << std::endl;

//  std::cout << (1 << 24) << std::endl;
/*  tree.insert(0);
  tree.insert(1);
  tree.insert(2);
  tree.insert(3);
  tree.insert(4);
  tree.insert(5);
  tree.insert(6);
  tree.insert(7);
  tree.insert(8);
  tree.insert(9);
  tree.insert(10);
  tree.deleteKey(0);
//  printf("remove 1\n");
  tree.deleteKey(1);
  tree.deleteKey(2);
  std::ostringstream out;
  out << "digraph {\n";
  tree.dotString(out);
  out << "}\n";

  std::cout << out.str() << std::endl; */
/*
  RBTree<int, Node*> rbtree;

  rbtree.insert(1, new Node(1));
  rbtree.insert(3, new Node(3));
  rbtree.insert(2, new Node(2));
  rbtree.insert(6, new Node(6));
  rbtree.insert(1<<12, new Node(1<<12));
  rbtree.insert((3<<16)+1, new Node((3<<16)+1));
  rbtree.insert((3<<16)+2, new Node((3<<16)+2));
  rbtree.insert(23, new Node(24));

  std::cout << rbtree.findNext(23).r->x << std::endl; */
#ifdef linux
  // no need to sleep in linux ^^
#else
  _getch();
#endif
}
